package com.aynu.tree;

import java.util.ArrayList;

/**
 * @author mj
 * @version 1.0
 * @date 2020/12/23 22:39
 * 二叉树的之字遍历
 */
public class Solution {

    public static void main(String[] args) {
        //System.out.println("Hello Wolrd!");
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution s = new Solution();
        System.out.println(s.zigzagLevelOrder(root));
    }

    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
        if (root == null)
            return arr;

        zigzagLevelHelper(root, 0, arr);
        return arr;
    }

    //递归版实现二叉树的层次遍历(之字形遍历)
    public void zigzagLevelHelper(TreeNode root, int level, ArrayList<ArrayList<Integer>> arr) {
        if (root == null)
            return;
        if (level == arr.size()) {
            ArrayList<Integer> newlevelResult = new ArrayList<>();
            if (level % 2 == 0)                   //偶数层
                newlevelResult.add(root.val);
            else                             //奇数层
                newlevelResult.add(0, root.val);
            arr.add(newlevelResult);
        } else {
            ArrayList<Integer> levelResult = arr.get(level);
            if (level % 2 == 0)
                levelResult.add(root.val);
            else
                levelResult.add(0, root.val);
            arr.set(level, levelResult);
        }
        //递归遍历左右节点
        zigzagLevelHelper(root.left, level + 1, arr);
        zigzagLevelHelper(root.right, level + 1, arr);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
